#region Copyright Notice
// 
// 
//  
//  Copyright (c) 2009-2011 Anindya Chatterjee
//  
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//  
//      http://www.apache.org/licenses/LICENSE-2.0
//  
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
// 
// 
#endregion
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using AbstractClass.Extensions.Serialization;
using AbstractClass.Linq;

namespace AbstractClass.Collections.Generic
{
    /// <summary>
    /// Represents a data structure that emulates a hierarchical
    /// tree structure with a set of linked nodes.
    /// </summary>
    /// <typeparam name="T">The type of the data in the <see cref="Tree&lt;T&gt;"/>. </typeparam>
    [Serializable]
    public class Tree<T> : AbstractTree<T, TreeNode<T>>
    {
        private readonly List<TreeNode<T>> _leafNodes = new List<TreeNode<T>>();

        #region Overrides of AbstractTree<T,TreeNode<T>>

        /// <summary>
        /// Gets the leaf nodes of the tree.
        /// </summary>
        /// <value>The leaf nodes.</value>
        public override IEnumerable<TreeNode<T>> Leaves
        {
            get { return Root == null ? null : _leafNodes; }
        }

        /// <summary>
        /// Gets all nodes in the tree.
        /// </summary>
        /// <value>The nodes in the tree.</value>
        public override IEnumerable<TreeNode<T>> ToEnumerable
        {
            get { return Root == null ? null : Root.ToEnumerable(TraversalOrder.DepthFirst); }
        }

        /// <summary>
        /// Gets or sets the collection of <see cref="TreeNode&lt;T&gt;"/> at a specified depth.
        /// </summary>
        /// <value></value>
        public IEnumerable<TreeNode<T>> this[int depth]
        {
            get { return Root.ToEnumerable(TraversalOrder.DepthFirst).Where(x => x.Depth == depth); }
            set
            {
                foreach (var treeNode in value)
                {
                    AddNode(treeNode, depth);
                }
            }
        }

        /// <summary>
        /// Clears this instance and remove all the nodes attached to it.
        /// </summary>
        public override void Clear()
        {
            if (Root == null) return;
            Root.Delete();
            Root = null;
        }

        /// <summary>
        /// Gets the sub-tree rooted at <paramref name="node"/>.
        /// </summary>
        /// <param name="node">The root node of the sub-tree.</param>
        /// <returns>
        /// A <see cref="AbstractTree&lt;T, TNode&gt;" /> object with <paramref name="node"/> at its root.
        /// </returns>
        public override AbstractTree<T, TreeNode<T>> GetSubtree(TreeNode<T> node)
        {
            var subTree = new Tree<T> {Root = node};
            subTree._leafNodes.AddRange(_leafNodes.Where(x => subTree.ToEnumerable.Contains(x)));
            return subTree;
        }

        /// <summary>
        /// Creates a clone of this instance.
        /// </summary>
        /// <returns>
        /// A new <see cref="AbstractTree&lt;T, TNode&gt;" /> object, which is a clone of this instance.
        /// </returns>
        public override AbstractTree<T, TreeNode<T>> Clone()
        {
            try
            {
                Stream stream = this.ToBinaryStream();
                Tree<T> newTree = this.FromBinaryStream(stream);
                return newTree;
            }
            catch
            {
                return MemberwiseClone() as Tree<T>;
            }
        }

        /// <summary>
        /// Adds the node to the tree.
        /// </summary>
        /// <param name="node">The node to add.</param>
        /// <returns>
        /// <c>true</c> if added successfully; otherwise, <c>false</c>.
        /// </returns>
        public override bool AddNode(TreeNode<T> node)
        {
            return AddNode(node, -1);
        }

        /// <summary>
        /// Adds the node to the <see cref="Tree&lt;T&gt;"/>.
        /// </summary>
        /// <param name="node">The node to add.</param>
        /// <param name="depth">The depth at which the node to be attached.</param>
        /// <returns>
        /// <c>true</c> if added successfully; otherwise, <c>false</c>.
        /// </returns>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="depth"/> is greater than the
        /// height of the <see cref="Tree&lt;T&gt;"/>.</exception>
        public override bool AddNode(TreeNode<T> node, int depth)
        {
            TreeNode<T> firstNode = _leafNodes.FirstOrDefault();
            if (node.ChildCount == 0)
                _leafNodes.Add(node);

            if (Root == null)
            {
                Root = node;
                node.Depth = 0;
                node.Parent = null;
                return true;
            }

            if (depth == -1)
            {
                firstNode.AddChild(node);
                _leafNodes.Remove(firstNode);
                return true;
            }

            if (depth == 0)
            {
                TreeNode<T> root = Root;
                node.AddChild(root);
                Root = node;
                node.Parent = null;
                if (root.ChildCount == 0)
                    _leafNodes.Add(root);
                Root.Depth = 0;
                return true;
            }

            IEnumerable<TreeNode<T>> nodes = Root.ToEnumerable(TraversalOrder.DepthFirst);
            if (nodes != null)
            {
                if (depth > nodes.Max(x => x.Depth))
                    throw new ArgumentOutOfRangeException("depth", LanguageResource.NodeDepthCantBeGreater);

                var parent = (TreeNode<T>) nodes.FirstOrDefault(treeNode => treeNode.Depth == depth).Parent;
                parent.AddChild(node);
                return true;
            }
            return false;
        }

        /// <summary>
        /// Deletes the node from the tree.
        /// </summary>
        /// <param name="node">The node to delete.</param>
        /// <returns>
        /// <c>true</c> if deleted successfully; otherwise, <c>false</c>.
        /// </returns>
        public override bool DeleteNode(TreeNode<T> node)
        {
            try
            {
                var parent = (TreeNode<T>) node.Parent;

                if (!node.Children.IsNullOrEmpty())
                {
                    TreeNode<T> newNode = node.Children[0];
                    node.Children.Remove(newNode);
                    newNode.AddChildren(node.Children);

                    if (parent != null)
                    {
                        parent.AddChild(newNode);
                        parent.RemoveChild(node);
                        if (parent.ChildCount == 0)
                            _leafNodes.Add(parent);
                    }
                    else
                    {
                        Root = newNode;
                        newNode.Parent = null;
                    }
                }
                else
                {
                    _leafNodes.Remove(node);
                    if (parent != null)
                    {
                        parent.RemoveChild(node);
                        if (parent.ChildCount == 0)
                            _leafNodes.Add(parent);
                    }
                    else
                        Root = null;
                }

                return true;
            }
            catch
            {
                return false;
            }
        }

        /// <summary>
        /// Tries to get the node specified by <paramref name="data"/> from the tree.
        /// </summary>
        /// <param name="data">The data to search.</param>
        /// <returns>
        /// A <see cref="TreeNode&lt;T&gt;"/> object associated with <paramref name="data"/>
        /// if fetching successful; otherwise, <c>null</c>.
        /// </returns>
        public override TreeNode<T> TryGetNode(T data)
        {
            return Root == null ? null : Root.HasDescendant(data);
        }

        /// <summary>
        /// Determines whether the specified <paramref name="node"/> is in the tree or not.
        /// </summary>
        /// <param name="node">The node to find.</param>
        /// <returns>
        /// 	<c>true</c> if the tree has the specified node; otherwise, <c>false</c>.
        /// </returns>
        public override bool HasNode(TreeNode<T> node)
        {
            return Root != null && Root.ToEnumerable(TraversalOrder.DepthFirst).Contains(node);
        }

        /// <summary>
        /// Traverses the whole tree in a order specified by <see cref="TraversalOrder"/> and executes an <see cref="Action&lt;T&gt;"/> specified by
        /// <paramref name="treeVisitor"/> in each node once.
        /// </summary>
        /// <param name="treeVisitor">The tree visitor which will get executed at each node of the tree once.</param>
        /// <param name="traversalOrder">Order of the tree traversal.</param>
        public void Traverse(Action<TreeNode<T>> treeVisitor, TraversalOrder traversalOrder)
        {
            if (Root == null) return;
            Root.ToEnumerable(traversalOrder).Process(treeVisitor);
        }

        #endregion
    }
}